//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 
//
// 示例 1： 
//
// 输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
// 
//
// 示例 2： 
//
// 输入: "cbbd"
//输出: "bb"
// 
// Related Topics 字符串 动态规划 
// 👍 2906 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <=1) {
            return s;
        }
        String str="";
        for (int i = 0; i < s.length(); i++) {
            int j=i-1;//奇数情况
            int k=i+1;
            while(j>=0&&k < s.length()&&s.charAt(j) ==s.charAt(k)) {
                j--;
                k++;
            }
                if(str.length()<(k-j-1))
                str=s.substring(j+1,k);//截取上一个字符串


            j=i;
            k=i+1;
            while (j>=0&&k<s.length() && s.charAt(j) == s.charAt(k)) {
                j--;
                k++;
            }
                if(str.length()<(k-j-1))
                str=s.substring(j+1,k);//截取上一个字符串
        }
        return str;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
